package util;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * A util class for making summary. Usage: Summary s=new Summary();
 * s.setSummaryLength(30); String r1=s.getSummary("��������","���������"); //or
 * String r = s.getSummary("****", "** **", "Image"); Notice: divide request
 * into terms by Term_List_Separator //default ' '
 */

@SuppressWarnings("unchecked")
public class Summary {
    public static class SummaryPolicy {
        // minimum length of sentences, sentence threshold 1
        // if length is great than threshold 1 and sentence divider meet, then divide it.
        public final int SEN_THRESHOLD_1;
        // if length is great than threshold 2 and sentence SUB divider meet, then divide.
        public final int SEN_THRESHOLD_2;
        // if sentence with length greater than it is preferred.
        // it's something like a threshold, NOT a favorite number. 
        public final int PREFERRED_SEN_LENGTH;
        // discard consecutive sequence like "###########"
        public final int MAX_CONSECUTIVE_NUM;
        // max segment count for a summary
        public final int MAX_SEGMENT_COUNT;
        /** 
         * tolerance in length of final summary, meaning that the final summary need not to
         * be exactly the same length of give length, but be slightly different from that
         * fixed value when needed.
         */ 
        public final int LENGTH_TOLERANCE;
        // define the max length of block, if it exceeds, the algorithm feels free to 
        // cut off even in the middle of the block.
        public final int MAX_BLOCK_LENGTH;
        // max distance when finding paired chars
        public final int MAX_PAIR_DISTANCE;
        // the first few letters are preserved, to avoid the first few letters being
        // replaced by "...", so that user can get a better view of the summary. 
        public final int PRESERVE_FRONT;
        // range that a attractive term or inattractive suspension will affect.
        public final int TERM_AFFECT_RANGE;
        // revise length
        public final int SUMMARY_REVISE_LENGTH;

        /**
         * 
         * @param sen_threshold_1
         * @param sen_threshold_2
         * @param preferred_sen_length
         * @param max_consecutive_num
         * @param max_segment_count
         * @param length_tolerance
         * @param max_block_length
         * @param preserve_front
         * @param term_affect_range
         * @param summary_revise_length
         */
        public SummaryPolicy(int sen_threshold_1, int sen_threshold_2, 
                int preferred_sen_length, int max_consecutive_num, 
                int max_segment_count, int length_tolerance, 
                int max_block_length, int max_pair_distance, 
                int preserve_front, int term_affect_range, int summary_revise_length) {
            SEN_THRESHOLD_1 = sen_threshold_1;
            SEN_THRESHOLD_2 = sen_threshold_2;
            PREFERRED_SEN_LENGTH = preferred_sen_length;
            MAX_CONSECUTIVE_NUM = max_consecutive_num;
            MAX_SEGMENT_COUNT = max_segment_count;
            LENGTH_TOLERANCE = length_tolerance;
            MAX_BLOCK_LENGTH = max_block_length;
            MAX_PAIR_DISTANCE = max_pair_distance;
            PRESERVE_FRONT = preserve_front;
            TERM_AFFECT_RANGE = term_affect_range;
            SUMMARY_REVISE_LENGTH = summary_revise_length;
        }
    }
    
    public static enum CharType {
        SENTENCE_SEPARATOR, // sentence separator
        SUBSENTENCE_SEPARATOR, // sub-sentence separator
        OTHER_CHAR
        // other character
    }
    
    // some specific types of summary
    public static enum SummaryType {
        WEB_SEARCH_SUMMARY,
        BLOG_SEARCH_SUMMARY,
        IMAGE_SEARCH_SUMMARY,
    }
    
    // some predefined policy
    public static final SummaryPolicy longSummaryPolicy;
    public static final SummaryPolicy shortSummaryPolicy;
    
    // thresshold for short and long summary
    public static final int LONG_SUMMARY_THRESHOLD = 25;

    // default value for summary width and sentence length.
    public static final int DEFAULT_SUMMARY_LENGTH = 100;
    
    // default value for max length of sentence
    public static final int DEFAULT_MAX_SENTENCE_LENGTH = 120;
   
    // the max occurrence of terms in request
    public static final int MAX_TERM_COUNT = 100;

    // summary length upperbound;
    private static final int SUMMARY_LENGTH_UPPER_BOUND = 1000000;
    // sentence dividers
    private static final String SEN_DIVIDERS = ".!?。？！\n\r";

    // String senSubDividers = "\t>,\'\";:| ，“’：；｜"; // sub-sentence dividers
    static final String SEN_SUBDIVIDERS = "\t,;: ，；："; // sub-sentence
    
    // all dividers
    // private static final String ALL_DIVIDERS = SEN_DIVIDERS + SEN_SUBDIVIDERS;

    // chars not wanted to appear immediately after a suspension. such as 。，
    private static final String notAfterSuspension;

    // to be initialized when instance of Summary being constructed
    private static final String leftBraces;

    // dividers
    // private static final String allPunctuations = ".!?。？！><,\'\";: ，“’：；(（";

    private static final String rightBraces;
    private static final String suspension = "..."; // the '...'

    // connected chars, see details in isConnectedChar.
    private static final String CONNECTED_CHARS = "%_.:/~?&=-";

    // left braces
    public static final char ucsLeftBraces[] = {
        '(', '[', '{', '<', '\"', '\'', 0x2018, // chinese left single quotation
        // mark -- ‘
        0x201c, // chinese left double quotation mark -- “
        0x3008, // chinese left angle bracket -- 〈
        0x300a, // chinese left double angle bracket -- 《
        0x300c, // chinese left corner bracket -- 「
        0x300e, // chinese left white corner bracket -- 『
        0x3010, // chinese left black lenticular bracket -- 【
        0x3014, // chinese left tortoise shell bracket -- 〔
        0x3016, // chinese left white lenticular bracket -- 〖
        0xff08, // chinese （
        0xff5b
    // chinese ｛
    };

    // right braces
    public static final char ucsRightBraces[] = {
        ')', ']', '}', '>', '\"', '\'', 0x2019, // chinese right single
        // quotation mark -- ’
        0x201d, // chinese right double quotation mark -- ”
        0x3009, // chinese right angle bracket -- 〉
        0x300b, // chinese right double angle bracket -- 》
        0x300d, // chinese right corner bracket -- 」
        0x300f, // chinese right white corner bracket --』
        0x3011, // chinese right black lenticular bracket -- 】
        0x3015, // chinese tortoise shell bracket -- 〕
        0x3017, // chinese right white lenticular bracket -- 〗
        0xff09, // chinese ）
        0xff5d
    // chinese ｝
    };

    // pixel width of single chinese character.
    public static final int HANZI_WIDTH = 255;

    // from 0-255, 255 means the width of Chinese charater
    public static final int CHAR_WIDTH[] = {/* */
        78,
        /* ! */59,
        /* " */98,
        /* # */151,
        /* $ */138,
        /* % */237,
        /* & */178,
        /* ' */39,
        /* ( */78,
        /* ) */78,
        /***/
        98,
        /* + */158,
        /* ' */78,
        /*-*/78,
        /* . */78,
        /* / */136,
        /* 0 */136,
        /* 1 */136,
        /* 2 */136,
        /* 3 */136,
        /* 4 */136,
        /* 5 */136,
        /* 6 */136,
        /* 7 */136,
        /* 8 */136,
        /* 9 */136,
        /* : */78,
        /* ; */78,
        /* < */158,
        /* = */158,
        /* > */158,
        /* ? */136,
        /* @ */255,
        /* A */178,
        /* B */178,
        /* C */178,
        /* D */178,
        /* E */178,
        /* F */158,
        /* G */195,
        /* H */178,
        /* I */59,
        /* J */117,
        /* K */178,
        /* L */138,
        /* M */216,
        /* N */178,
        /* O */195,
        /* P */178,
        /* Q */195,
        /* R */178,
        /* S */178,
        /* T */138,
        /* U */178,
        /* V */178,
        /* W */255,
        /* X */138,
        /* Y */178,
        /* Z */138,
        /* [ */78,
        /* \ */78,
        /* ] */78,
        /* ^ */98,
        /* _ */138,
        /* ` */78,
        /* a */138,
        /* b */138,
        /* c */138,
        /* d */138,
        /* e */138,
        /* f */59,
        /* g */138,
        /* h */138,
        /* i */59,
        /* j */59,
        /* k */138,
        /* l */59,
        /* m */216,
        /* n */138,
        /* o */138,
        /* p */138,
        /* q */138,
        /* r */79,
        /* s */138,
        /* t */79,
        /* u */138,
        /* v */98,
        /* w */178,
        /* x */138,
        /* y */138,
        /* z */138,
        /* { */78,
        /* | */59,
        /* } */78,
        /* ~ */158
    };

    // set if is sentence separator or sub-sentence separator
    public static final int CHARFLAG_SEPTYPE = 1;

    // set if is sentence separator
    public static final int CHARFLAG_SENSEP = 2;

    // set if both previous and current chars' CHARFLAG_SEPTYPEs are set
    public static final int CHARFLAG_DUALSEP = 4;

    // set if char is A...Z, a..z
    public static final int CHARFLAG_ALPHABET = 8;

    // set if char is 0..9
    public static final int CHARFLAG_DIGIT = 16;

    // set if is Chinese char
    public static final int CHARFLAG_CHINESE = 32;

    // set if is '.'
    public static final int CHARFLAG_DOT = 128;

    // set if is '@'
    public static final int CHARFLAG_AT = 256;

    // punctions that can be removed while revising.
    private static final String REVISE_PUNCTIONS = "";
        //",.!?。？！\n\r\t;，；"; // now, use empty set to avoid introducing new bugs.
        //".!?。？！\n\r\t,;:，；：、"; // subDivider + divider + '、‘ - ’ ‘
    
    
    // width of suspension, initialized in static statments
    private static final int suspensionWidth; // the width of suspension

    // flag for suspension, useful when add suspensions.
    private static final int FLAG_SUSPENSION = -1;
    
    // flag for blank area.
    private static final int FLAG_BLANK = -2;

    /**
     * static initialization for static final variables
     */
    static {
        suspensionWidth = getStringWidth(suspension);
        leftBraces = new String(ucsLeftBraces);
        rightBraces = new String(ucsRightBraces);
        notAfterSuspension = "：.。!！?？,，；、" + rightBraces;
//        private static final int SEN_THRESHOLD_1_FOR_LONG = 8;
//        private static final int SEN_THRESHOLD_1_FOR_SHORT = 4;
//        
//        private static final int SEN_THRESHOLD_2_FOR_LONG = 40;
//        private static final int SEN_THRESHOLD_2_FOR_SHORT = 8;
//        
//        private static final int PREFERRED_SEN_LENGTH_FOR_LONG = 8;
//        private static final int PREFERRED_SEN_LENGTH_FOR_SHORT = 5;
//        
//        private static int MAX_CONSECUTIVE_NUM = 5;
//
//        private static final int MAX_SEGMENT_COUNT_FOR_LONG = 3;
//        private static final int MAX_SEGMENT_COUNT_FOR_SHORT = 1;
//
//        private static final int LENGTH_TOLERANCE_FOR_LONG = 5;
//        private static final int LENGTH_TOLERANCE_FOR_SHORT = 5;
//        
//        private static final int MAX_BLOCK_LENGTH_FOR_LONG = 40 (SEN_THRESHOLD_2_FOR_LONG);
//        private static final int MAX_BLOCK_LENGTH_FOR_SHORT = 10;
//        
//        private static final int PRESERVE_FRONT_FOR_LONG = 0;
//        private static final int PRESERVE_FRONT_FOR_SHORT = 0;
//
//        private static final int TERM_AFFECT_RANGE = 6;
//        private static final int SUMMARY_REVISE_LENGTH_FOR_LONG = 3;
//        private static final int SUMMARY_REVISE_LENGTH_FOR_SHORT = 1;
//
        /*
         * @param max_sentence_length
         * @param sen_threshold_1
         * @param sen_threshold_2
         * @param preferred_sen_length
         * @param max_consecutive_num
         * @param max_segment_count
         * @param length_tolerance
         * @param max_block_length
         * @param max_pair_distance
         * @param preserve_front
         * @param term_affect_range
         * @param summary_revise_length
         */
        // for web and blog summary;
        longSummaryPolicy = new SummaryPolicy(8, 40, 8, 5, 3, 5, 40, 20, 10, 6, 3);
        // for image summary;
        shortSummaryPolicy = new SummaryPolicy(4, 8, 5, 5, 1, 5, 10, 16, 6, 6, 4);
    }
    /**
     * Divide terms
     * @param request
     * @return
     */
    private static List<Term> divideTerms(String request) {
        List<Term> termList = new ArrayList<Term>();
        int sepPos = 0, requestLength = request.length();

        while (sepPos < requestLength) {
            // deal with blanks at begin
            while ((sepPos < requestLength)
                    && (request.charAt(sepPos) == Term.TERM_LIST_SEPARATOR))
                sepPos++;
            if (sepPos == requestLength)
                break;
            assert (termList.size() < MAX_TERM_COUNT);
            Term term = new Term(request, sepPos);
            termList.add(term);
            sepPos += term.length;
        }
        return termList;
    }

    /**
     * "distance" generated by a char, which indeed mean: a new subsentence starts,
     * or a new sentence starts, or a new paragraph starts.
     * @param ch
     * @return
     */
    private static int getCharDistance(char ch) {
        int distance = 0;
        switch (ch) {
            case '\n':
                distance = 256;
                break;
            case '.':
            case '?':
            case '!':
            case 0x3002: // ucs2 code of chinese full stop
            case 0xff1f: // ucs2 code of chinese question mark
            case 0xff01: // ucs2 code of chinese excalmatroy mark
                distance = 128;
                break;
            case ',':
            case ';':
            case 0xff0c: // ucs2 code of chinese comma
            case 0xff1b: // ucs2 code of chinese semicolon
                distance = 64;
                break;
            case ' ':
                distance = 32;
                break;
        }// switch

        return distance;
    }

    public static int getCharFlags(char prev, char current) {
        CharType curType = getCharType(current);
        int flags = 0;
        if ((curType == CharType.SENTENCE_SEPARATOR)
                || (curType == CharType.SUBSENTENCE_SEPARATOR)) {
            flags |= CHARFLAG_SEPTYPE;
        } // if
        if (curType == CharType.SENTENCE_SEPARATOR) {
            flags |= CHARFLAG_SENSEP;
        } // if
        if (Character.isDigit(current)) {
            flags |= CHARFLAG_DIGIT;
        } // if
        if (Character.isLetter(current)) {
            flags |= CHARFLAG_ALPHABET;
        } // if
        if ((current & 0x7F) != current) {
            flags |= CHARFLAG_CHINESE;
        } // if
        if ('@' == current) {
            flags |= CHARFLAG_AT;
        } // if
        if ('.' == current) {
            flags |= CHARFLAG_DOT;
        } // if

        if (prev == 0) {
            return flags;
        }// if

        // additional flags for previous char
        CharType prevType = getCharType(prev);
        if (((prevType == CharType.SENTENCE_SEPARATOR || prevType == CharType.SUBSENTENCE_SEPARATOR))
                && ((curType == CharType.SENTENCE_SEPARATOR) || (curType == CharType.SUBSENTENCE_SEPARATOR))) {
            flags |= CHARFLAG_DUALSEP;
        }// if

        return flags;
    }
    private static CharType getCharType(char ch) {
        // see if ch is in senDividers
        if (SEN_DIVIDERS.indexOf(ch) > -1)
            return CharType.SENTENCE_SEPARATOR;
        // see if ch is in senSubDividers
        if (SEN_SUBDIVIDERS.indexOf(ch) > -1)
            return CharType.SUBSENTENCE_SEPARATOR;
        // the default character type
        return CharType.OTHER_CHAR;
    }
    
    // get width of a character.
    private static int getCharWidth(char ch) {
        if (ch > 0x00ff) // Hanzi
            return 255;
        else if (ch >= 0x7f) // CHAR_WIDTH starts with ' ', so return a width
            // of space
            return CHAR_WIDTH[0];
        else if (ch >= 0x20) // 0x20..0x7e widthCHARFLAG_DUALSEP defined in CHAR_WIDTH[]
            return CHAR_WIDTH[ch - ' '];
        return CHAR_WIDTH[0]; // all control character, return one space
    }

    // get width of a string.
    public static int getStringWidth(String s) {
        int len = 0;
        for (int i = 0; i < s.length(); i++)
            len += getCharWidth(s.charAt(i));
        return len;
    }

    /**
     * whether it is a char that "connected" to previous and succeeding connected chars.
     * which means, reserve or remove them together when adding suspension.
     * 
     * @param ch
     * @return
     */
    private static boolean isConnectedChar(char ch) {
        return isEngLetter(ch) || isDigit(ch)
                || CONNECTED_CHARS.indexOf(ch) >= 0;
    }

    /**
     * whether a char is considered to be candidate of ConsecutiveChar.
     */ 
    private static boolean isConsecutiveChar(char ch) {
        return ((ch >= 0x20 && ch < 0x30) || (ch > 0x39 && ch < 0x41)
                || (ch > 0x5a && ch < 0x61) || (ch > 0x7a && ch < 0x7f)
                || (ch >= 0x80 && ch <= 0xff) // latin supplement
                || (ch >= 0x2000 && ch <= 0x206f) // general punctuation
                || (ch >= 0x3000 && ch <= 0x303f) // cjk symbols and
        // punctuation
        || (ch >= 0x2500 && ch <= 0x257f) // box drawing
        );
    }
    
    // whether it is a digit
    private static boolean isDigit(char ch) {
        return (ch >= 0x30 && ch <= 0x39);
    }

    // whether it is a English letter
    private static boolean isEngLetter(char ch) {
        return ((ch >= 0x61 && ch <= 0x7a) || (ch >= 0x41 && ch <= 0x5a));
    }

    // whether it is a English letter or a digit
    private static boolean isLetterOrDigit(char ch) {
        return (isEngLetter(ch) || isDigit(ch));
    }

    public static void main(String[] args) {
        String[] tm = {
            "我们", "我们", "爽 啊", "A B", "600748", "你们"
        };
        String[] tt = {
            "你侧 苏梦枕接着对众人道:我为什么要选和非正式家族合作。我们#####折林木,复有白虹贯于岩壑.不能.。师 认为哦我们",
            "内容报道合作—欢迎各类媒体、影视剧公司、制作公司、专业网站、出版社、协会等与我们联系，我们在各类文字、图片、音视频资讯等方面建立长期合作。活动合作—欢迎各方与新浪网洽谈推广会议、论坛、演唱会、大奖赛、巡展或体育赛事等各类活动。通过新浪的报道推广，扩大相关活动的影响力。",
            "爽啊真的马真的马真的马。啊啊啊啊啊啊啊啊啊啊啊啊啊啊呵！",
            "Azzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz. Bzzzzzzzzzzzzzzzzzzzzzzzzzzzzz. AAAzzzzzzzzzzzzzzzz",
            "c上实发展[600748]\n☆最新提示☆ ◇港澳资讯600748 更新日期：2007-06-30◇ 灵通V4.0｜\n★最新公告:06-30日刊登资产转让公告。(详见后) ｜｜★最新报道:06-13日上实发展(600748)圣彼得堡项目进展顺利 。(详见后)",
            "你们好-----哈哈哈哈"
        };
        Summary s = new Summary();
        int index = 5;
        s.setSummaryLength(110);
        String request = tm[index];
        String text = tt[index];
        String result = s.getSummary(request, text);
        System.out.println("-- Result --");
        System.out.println(result);
        System.out.println(result.length());
    }

    /**
     * filter non-display character. here, just '\n' others are filered out when doing
     * preFilter(). 
     */
    private static StringBuilder postFilter(StringBuilder text) {
        int i = 0;
        while (i < text.length()) {
            if (text.charAt(i) == '\n')
                text.setCharAt(i, ' ');
            i++;
        }
        return text;
    }

    /**
     * filter useless character that can not be displayed on the screen. '\n' is
     * NOT filtered out, since this process is before generating summary, '\n' is 
     * useful in generating a better summary.
     * in postFilter, we remove '\n';
     */
    private static String preFilter(StringBuilder text, SummaryPolicy policy) {
//        boolean inBlock = false;
//        boolean divided = true;
//        int bracePosition = Integer.MAX_VALUE;
        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            if (c != '\n' && c < 32 || (c >= 0xa0 && c <= 0xff)
                    || (c >= 0xd800 && c <= 0xf8ff)
                    || (c >= 0x2100 && c <= 0x28ff) || c >= 0xfff0
                    || c == 0x3000) {
                // filter out characters that cannot display, alter them to
                // SPACE
                text.setCharAt(i, ' ');
            } else if (c >= 0x2011 && c <= 0x2015) {
                // replace dash symbols to hyphen
                text.setCharAt(i, '-');
            }
        } // for i
        
        // move redundant spaces and consecutive chars from text
        int consCount = 1;
        boolean isBegin = true; // is this char appear at begin?
        boolean isPreSpaceChar = false; // is previous char space?
        char ch, preCh = 0;
        int i = 0;
        while (i < text.length()) {
            ch = text.charAt(i);
            if (isBegin && !Character.isSpaceChar(ch)) {
                isBegin = false;
            } 
            // leave only one space char in the middle
            if (Character.isSpaceChar(ch)) {
                if (isPreSpaceChar || isBegin) {
                    text.deleteCharAt(i);
                } else i++;
                isPreSpaceChar = true;
                consCount = 1;
            } else {
                isPreSpaceChar = false;
                if (i > 0 && isConsecutiveChar(ch) && ch == preCh)
                    consCount++;
                else
                    consCount = 1;
                if (consCount == policy.MAX_CONSECUTIVE_NUM) {
                    int startToDelete = i - policy.MAX_CONSECUTIVE_NUM + 1;
                    while (i < text.length() && text.charAt(i) == ch) {
                        i++;
                    }
                    text.delete(startToDelete, i);
                    i = startToDelete;
                    text.insert(i++, ' ');
                    isPreSpaceChar = true;
                } else {
                    i++;
                }
            } // else
            preCh = ch;
        }// while
        return text.toString();
    }

    // global variables;
    private final Map<Integer, List<Term>> map = new HashMap<Integer, List<Term>>();

    /*
     * length and width wanted, use setSummaryLength to set length, summaryWidth is 
     * automatically set to summaryLength * HANZI_WIDTH; 
     */ 
    private int summaryLength = DEFAULT_SUMMARY_LENGTH;

    private int summaryWidth = DEFAULT_SUMMARY_LENGTH * HANZI_WIDTH;
    
    private int maxSentenceLength = DEFAULT_MAX_SENTENCE_LENGTH;

    // all terms
    List<Term> terms;

    // all sentences.
    List<Sentence> sentences;

    // result strings
    StringBuilder resultSummary;

    // actually width for final summary.
    private int actualWidth;
    
    // length threshold that a cut off operation can be performed. 
    private int MIN_CUT_OFF_LENGTH = 3;

    /**
     * constructor of Summary
     */
    public Summary() {
        summaryLength = DEFAULT_SUMMARY_LENGTH;
        maxSentenceLength = DEFAULT_MAX_SENTENCE_LENGTH;
    }

    /**
     * build flag array flag array is zero when the char is matched as part of a
     * term; is a value when is unmatched char and attractiveness is presented.
     * 
     * @param flag
     * @param text
     * @param pair
     * @param sentences
     * @param selected
     * @param susIndex
     * @param lengthTolerance
     */
    private void buildArrays(int[] flag, char[] text, int[] pair,
            List<Sentence> sentences, int[] selected, List<Integer> susIndex,
            int maxPairDistance, int maxBlockLength) {
        int initialFlag = -1;
        Arrays.fill(pair, initialFlag);
        int index = 0, flagId = 0;
        for (int i = 0; i < selected.length; i++) {
            if (i >= 1 && (selected[i] != selected[i - 1] + 1)) {
                susIndex.add(index);
                flag[index] = flag[index + 1] = flag[index + 2] = FLAG_SUSPENSION;
                text[index] = text[index + 1] = text[index + 2] = '.';
                pair[index] = index;
                pair[index + 1] = index + 1;
                pair[index + 2] = index + 2;
                index += 3;
            }
            Sentence sen = sentences.get(selected[i]);
            for (int j = 0; j < sen.termList.size(); j++) {
                int id = ++flagId;
                int termHead = index + sen.termPosList.get(j);
                int termTail = termHead + sen.termList.get(j).length;
                for (int k = termHead; k < termTail; k++) {
                    flag[k] = id;
                }
            }
            int senLen = sen.getLength();
            for (int j = 0; j < senLen; j++) {
                text[index + j] = sen.getCharAt(j);
            }
            int connectedIndex = index + 1;
            for (int j = index; j < index + senLen; j++) {
                if (pair[j] == initialFlag) {
                    int pairIndex = leftBraces.indexOf(text[j]);
                    if (pairIndex >= 0) {
                        char pairedChar = rightBraces.charAt(pairIndex);
                        int k = j + 1;
                        while (k < index + senLen && k < j + maxPairDistance) {
                            if (text[k] == pairedChar) {
                                pair[j] = k;
                                pair[k] = j;
                                break;
                            }
                            k++;
                        }
                        if (pair[j] == initialFlag)
                            pair[j] = j;
                    } else if (isConnectedChar(text[j])) {
                        if (connectedIndex < j)
                            connectedIndex = j;
                        while (connectedIndex < index + senLen - 1
                                && connectedIndex < j + maxBlockLength
                                && isConnectedChar(text[connectedIndex + 1])) {
                            connectedIndex++;
                        }
                        pair[j] = connectedIndex;
                        if (connectedIndex < index + senLen 
                                && connectedIndex < j + maxBlockLength
                                && pair[connectedIndex] == initialFlag)
                            pair[connectedIndex] = j;
                        // if (pair[connectedIndex - 1] == initialFlag)
                        // pair[connectedIndex - 1] = j;
                    } else {
                        pair[j] = j;
                    }
                }
            }
            index += senLen;
        }
    }

    /**
     * build final summary according to text and flag
     */
    private StringBuilder buildSummary(char[] text, int[] flag) {
        int length = text.length;
        StringBuilder sb = new StringBuilder(text.length);
        int i = 0;
        while (i < length) {
            if (flag[i] >= 0) {
                sb.append(text[i]);
                i++;
            } else if (flag[i] == FLAG_SUSPENSION){
                sb.append(suspension);
                while (i < length && flag[i] == FLAG_SUSPENSION)
                    i++;
            } else {
                i++;
                // DO NOTHING...
            }
        }
        return sb;
    }

    /**
     * add suspensions for a sequence of sentences, whose total width is
     * close to summaryWidth.
     * 
     * @param sentences
     * @param selected
     * @param maxSegmentCountAllowed
     * @param lengthTolerance
     * @param preserveFrontLength 
     */
    private StringBuilder composeSummary(List<Sentence> sentences, int[] selected,
            SummaryPolicy policy) {
        // we do not use selectFromStart..., just deal with it as a normal summary
        // but, something bad happened, so reuse 
        if (selected.length == 0 || noTermMatched()) {
            resultSummary = selectFromStart(sentences, policy.LENGTH_TOLERANCE);
            return resultSummary;
        }
        // original segmentCount, width, length
        int segmentCount = 1, width = 0, originalLength = 0;
        for (int i = 0; i < selected.length; i++) {
            if (i >= 1 && (selected[i] != selected[i - 1] + 1)) {
                segmentCount++;
                width += suspensionWidth;
                originalLength += 3;
            }
            Sentence sen = sentences.get(selected[i]);
            width += sen.getWidth();
            originalLength += sen.getLength();
        }
        int[] flag = new int[originalLength];
        char[] text = new char[originalLength];
        int[] pair = new int[originalLength];
        List<Integer> susIndex = new ArrayList<Integer>();
        buildArrays(flag, text, pair, sentences, selected, susIndex,
                policy.MAX_PAIR_DISTANCE, policy.MAX_PAIR_DISTANCE);
        /*
         * try to add suspension follow these rules: 1) terms are considered to
         * be attractive, chars near the terms are also attractive, the short
         * the distance is, the more attractive it is; 2) a single term can not
         * be partly removed. keep or remove the whole term. 3) ... is
         * considered not to be attractive 4) chars near "..." are not
         * attractive, the short the distance is, the less attractive it is; 5)
         * chars nearly before "..." are less attractive than chars nearly after
         * it. because, the chars before "..." are likely to be end of a
         * sentence. 6) the most important: final segment count after adding
         * suspensions can NOT be larger than MAX_SEGMENT_COUNT_FOR_LONG(SHORT).
         * we follow these steps: 1) remove inattractive chars before and after
         * "...". 2) if segment count is not so big, remove inattractive chars
         * in the mid of sentences. 3) if length is still larger than required
         * legnth, remove some terms near the segment that contains a
         * suspension, so that the segmentCount will not increase.
         */
        double[] attractive = new double[originalLength];
        // int length = originalLength;
        // compute attrativeness
        computeAttrativeness(flag, attractive, policy.TERM_AFFECT_RANGE);
        extendSuspension(text, flag, attractive, pair, susIndex, segmentCount,
                policy.LENGTH_TOLERANCE * HANZI_WIDTH);
        cutOffText(text, flag, attractive, pair, susIndex, policy);
        reviseSummary(text, flag, pair, attractive, susIndex, policy);
        // build final summary
        resultSummary = buildSummary(text, flag);
        return resultSummary;
    }

    /**
     * compute attractiveness according to the flag array.
     * @param flag
     * @param attractive
     * @param affectRange
     */
    private void computeAttrativeness(int[] flag, double[] attractive,
            int affectRange) {
        assert (flag.length == attractive.length);

        // take affectRange = 3 as an example
        // xyzTERMabc...haha --> 1 2 3 4 4 4 4 3 2 1 -1 -1 -1 -2 -3 -4 -5\
        //                             ^ affectRange + 1     ^ FLAG_SUSPENSION - 1
        // abc...def...ghi   --> -4 -3 -2 -1 -1 -1 -3 -3 -3 -1 -1 -1 -2 -3 -4
        //                                          ^ -(affectRange + 1)
        int length = flag.length;
        int start = 0;
        while (start < length) {
            int span = 0;
            while (start + span < length && flag[start + span] == 0) {
                span++;
            }
            // current interval [start, start + span - 1]
            if (start == 0) { // the first blank segment
                // matching nothing
                if (span == length) {
                    // this code should not be reached. this only happens when no term
                    // is found in the text. in that case, we use first few sentense 
                    // as summary. see in selectFromStart(...);
                    System.out.println("ERROR: Should not reach this line.");
                } else if (flag[span] > 0) { // blank before a term
                    for (int i = span - 1; i >= 0; i--)
                        attractive[i] = affectRange - (span - i) + 1;
                } else { // blank before suspension
                    for (int i = span - 1; i >= 0; i--)
                        attractive[i] = i - span - 1;
                }
            } else if (start + span >= length) { // the last blank segment
                if (flag[start - 1] > 0) { // a term to end
                    for (int i = start; i < length; i++)
                        attractive[i] = affectRange - (i - start);
                } else { // suspension to end
                    for (int i = start; i < length; i++)
                        attractive[i] = start - i - 2;
                }
            } else {
                if (flag[start - 1] > 0 && flag[start + span] > 0) {
                    // between 2 terms
                    int mid = start + (span + 1) / 2;
                    for (int i = start; i < mid; i++)
                        attractive[i] = affectRange - (i - start);
                    for (int i = mid; i < start + span; i++)
                        attractive[i] = affectRange - (start + span - i - 1);
                } else {
                    // between two suspensions or a term and a suspension
                    if (flag[start - 1] == FLAG_SUSPENSION && 
                            flag[start + span] == FLAG_SUSPENSION) {
                        // suspension to suspension 
                        for (int i = start; i < start + span; i++) {
                            attractive[i] = -affectRange;
                        }
                    } else {
                        if (flag[start - 1] > 0) {
                            // term to suspension
                            for (int i = start; i < start + span; i++) {
                                attractive[i] = affectRange - (i - start);
                            }
                        } else {
                            // suspension to term
                            for (int i = start; i < start + span; i++) {
                                attractive[i] = i - (start + span - 1) + affectRange;
                            }
                        }
                    }
                }
            }
            start += span;
            while (start < length && flag[start] != 0) {
                // attractiveness of chars inside a term is set to affectRange + 1.
                if (flag[start] > 0)
                    attractive[start] = affectRange + 1;
                start++;
            }
        }
    }

    // compute actually width for final summary 
    private void computeSummaryWidth() {
        actualWidth = 0;
        for (int i = 0; i < resultSummary.length(); i++) {
            actualWidth += getCharWidth(resultSummary.charAt(i));
        }
    }

    /**
     * remove a interval of current IS(initial summary), so as to make the width 
     * of summary acceptable
     * 
     * @param text,
     *      original text
     * @param flag
     *      flag for every char
     * @param attractive
     *      attractiveness for every char
     * @param pair
     *      for leftBrace, find appropriate index of rightBrace, for ordinary char, just
     *      set pair[i] = i;
     * @param affectRange
     *      the range that a term affects
     * @param maxSegmentCountAllowed
     *      the max segment count allowed 
     * @param lengthTolerance
     *      tolerance in length
     * @param susIndex
     *      current existing indice of suspensions
     */
    private void cutOffText(char[] text, int[] flag, double[] attractive,
            int[] pair, List<Integer> susIndex, SummaryPolicy policy) {
        int originalLength = text.length;
        int segmentCount = 0;
        int length = 0, width = 0;
        // recalculate length and width
        if (flag[0] == FLAG_SUSPENSION)
            segmentCount = 0;
        else
            segmentCount = 1;
        for (int i = 0; i < originalLength; i++) {
            if (flag[i] != FLAG_SUSPENSION) {
                if (i > 0 && flag[i - 1] == FLAG_SUSPENSION) {
                    segmentCount++;
                }
                length++;
                width += getCharWidth(text[i]);
            }
        }

        int widthTolerance = policy.LENGTH_TOLERANCE * HANZI_WIDTH;
        if (width >= summaryWidth + widthTolerance) {
//            int wantedLength = length - summaryLength;
            int wantedWidth = width - summaryWidth;
            // compute attrativeness
            computeAttrativeness(flag, attractive, policy.TERM_AFFECT_RANGE);
            // build sum array, to accelerate the computing of sum of an
            // interval.
            double[] sumOfAttr = new double[originalLength + 1];
            int[] sumOfWidth = new int[originalLength + 1];
            int[] remainedChars = new int[originalLength + 1];
            remainedChars[0] = 0;
            sumOfWidth[0] = 0;
            sumOfAttr[0] = 0;
            for (int i = 1; i <= originalLength; i++) {
                sumOfAttr[i] = sumOfAttr[i - 1] + attractive[i - 1];
                if (flag[i - 1] != FLAG_SUSPENSION) {
                    remainedChars[i] = remainedChars[i - 1] + 1;
                    sumOfWidth[i] = sumOfWidth[i - 1] + getCharWidth(text[i - 1]);
                } else {
                    remainedChars[i] = remainedChars[i - 1];
                    sumOfWidth[i] = sumOfWidth[i - 1];
                }
            }
            // minimize attractiveness, to find appropriate interval
            double minAttr = Integer.MAX_VALUE;
            int intLeft = 0, intRight = -1;
            // iterate every possible start of interval.
            // try to locate the right bound of interval, interval = [left, right];
            int deltaWidth = wantedWidth - widthTolerance > MIN_CUT_OFF_LENGTH  * HANZI_WIDTH? 
                    wantedWidth - widthTolerance : MIN_CUT_OFF_LENGTH * HANZI_WIDTH;
            int left = 0;
            int right = left - 1;
            //int right = policy.PRESERVE_FRONT + deltaIntervalLength - 1;
            while (sumOfWidth[originalLength] - sumOfWidth[left] > wantedWidth - widthTolerance) {
                // locate the right bound of interval
                if (right < left - 1) {
                    right = left - 1;
                }
                
                while (right + 1 < originalLength &&
                        sumOfWidth[right + 1] - sumOfWidth[left] < deltaWidth)
                    right = Math.max(right + 1, pair[right + 1]);
                
                if (right >= originalLength)
                    break;
                if (right < originalLength - 1) {
                    int nextRightBound = Math.max(right + 1, pair[right + 1]);
                    while (nextRightBound < originalLength - 1
                            && sumOfWidth[nextRightBound + 1] - 
                                sumOfWidth[left] <= wantedWidth + widthTolerance
                            && sumOfAttr[nextRightBound + 1] < 
                                sumOfAttr[right + 1]) {
                        right = nextRightBound;
                        nextRightBound = Math.max(right + 1, pair[right + 1]);
                    }
                }

                // skip serial of connected chars.
//                while (right < originalLength - 1
//                        && isConnectedChar(text[right + 1]))
//                    right = Math.max(right + 1, pair[right + 1]);
                
                if (right >= originalLength)
                    right = originalLength - 1;
                while (right < length - 1
                        && notAfterSuspension.indexOf(text[right + 1]) >= 0)
                    right++;
                /*
                 * check if interval [left, right] is going to introduce new
                 * segment, this is only allowed for segmengCount <
                 * MAX_SEGMENT_COUNT also check that length of interval is
                 * acceptable
                 */
                if (sumOfWidth[right + 1] - sumOfWidth[left] > wantedWidth - widthTolerance
                        && segmentCount < policy.MAX_SEGMENT_COUNT
                        || segmentCount == policy.MAX_SEGMENT_COUNT
                        && (right - left == remainedChars[right + 1]
                                - remainedChars[left]
                                || left == 0
                                || left > 0
                                && flag[left - 1] == FLAG_SUSPENSION
                                || right == length - 1 || right < length - 1
                                && flag[right + 1] == FLAG_SUSPENSION)) {
                    double weight = 1.0; 
                    if (intLeft < policy.PRESERVE_FRONT) {
                        weight = 1.0 / (policy.PRESERVE_FRONT - intLeft + 1);
                    }
                    if ((sumOfAttr[right + 1] - sumOfAttr[left]) * weight < minAttr) {
                        minAttr = (sumOfAttr[right + 1] - sumOfAttr[left]) * weight;
                        intLeft = left;
                        intRight = right;
                    }
                }
                left = Math.max(left, pair[left]) + 1;
            }
            // remove this interval.
            for (int i = intLeft; i <= intRight; i++) {
                width -= getCharWidth(text[i]);
                length--;
                flag[i] = FLAG_SUSPENSION;
            }
            // we do not care if it duplicated in array susIndex, just record it.
            if (intLeft <= intRight) 
                susIndex.add(intLeft);
        }
    }

    /**
     * Divide text to sentences
     * 
     * @param text
     * @param termList
     * @param senThreshold1 
     * @param senThreshold2 
     * @return
     */
    private List<Sentence> divideSentences(String text, List<Term> termList, SummaryPolicy policy) {
        map.clear();
        // reset local data
        List<Sentence> sentences = new ArrayList<Sentence>();
        sentences.clear();
        // record sentence distance.
        int sentDistance = 0;
        // matching states of terms
        int[] termStates = new int[termList.size()];
        // occurency of terms
        int[] termOccurs = new int[termList.size()];

        char curChar = 0; // the current char
        char preChar = 0; // previous char
        int senTermCount = 0; // the count of Terms (including duplicate
        // Terms)
        // in current sentence
        int curPos = 0; // current position in the text
        int senLen = 0; // current sentence's length
        int senWidth = 0; // current sentence's width

        // previous sentence.
        Sentence currentSentence = null, previousSentence = null;
        int senCount = 0;

        // for detect url, email address and other similar structure
        boolean inUrl = false;
        boolean inAlnum = false;
        boolean inBlock = false;
        int posBlock = 0;
        // for detect english word
        boolean inWord = false;
        // for detect numSerial
        boolean inNumSerial = false;
        // for divide long sentences not in terms.
        boolean inTerm = false;
        // to record term occurencies for current sentence
        List<Term> tempTermList = new ArrayList<Term>();
        List<Integer> tempTermPosList = new ArrayList<Integer>();
//        // wait a sentence divide or subdivider to break
//        boolean waitForBreak = false;

        // divide sentences and recognize Terms
        for (curPos = 0; curPos < text.length(); curPos++) {
            preChar = curChar;
            curChar = text.charAt(curPos);
            int charFlags = getCharFlags(preChar, curChar);

            if ((senLen == 0)
                    && ((charFlags & CHARFLAG_SEPTYPE) != 0 || Character
                            .isWhitespace(curChar))) {
                // a sentence should not start with a separator type
                // add last sentence distance
                sentDistance += getCharDistance(curChar);
                continue;
            } // if

            // recognizing url, email and something like abc.jpg ...
            if (isLetterOrDigit(curChar)) {
                inAlnum = true;
            } else if ('.' == curChar) {
                if (inAlnum) {
                    inUrl = true;
                } // if
            } else if ('@' == curChar) {
                if (inAlnum) {
                    inUrl = true;
                } // if
            } else {
                inUrl = false;
                inAlnum = false;
            } // else

            // this char is in a word or a num serial ?
            inWord = false;
            inNumSerial = false;
            if ((curPos + 1) < text.length())
                if (isEngLetter(curChar)
                        && isEngLetter(text.charAt(curPos + 1)))
                    inWord = true;
                else if (isDigit(curChar) && isDigit(text.charAt(curPos + 1)))
                    inNumSerial = true;

            senLen++;
            senWidth += getCharWidth(curChar);

            if (!(((senLen > 1 && curChar == '\n') || 
                    ((senLen > policy.SEN_THRESHOLD_1) && ((charFlags & CHARFLAG_SENSEP) != 0) && 
                            !inUrl && !inBlock && !inWord && !inNumSerial)) || 
                    ((senLen > policy.SEN_THRESHOLD_2) && ((charFlags & CHARFLAG_SEPTYPE) != 0) && 
                            !inUrl && !inBlock && !inWord && !inNumSerial))) {
                // curChar is not the end of a sentence, go on recoginzing Terms
                inTerm = false;

                for (int i = 0; i < termList.size(); i++) {
                    Term term = termList.get(i);
                    while (true) {
                        char termCurChar = term.getCharAt(termStates[i]);
                        if (Character.toLowerCase(curChar) == Character
                                .toLowerCase(termCurChar)) {
                            // curChar is the next char of i'th Term

                            inTerm = true; // current char is in some term
                            termStates[i]++;
                            if (termStates[i] >= term.length) {
                                // a Term has been recognized, reset the state
                                termStates[i] = 0;
                                inTerm = false;

                                // the start position of this Term
                                int head = (int) (curPos - term.length + 1);

                                // check if the place this Term taking is
                                // already taken
                                // by an earlier Term
                                List<Term> matchedTermList;
                                // write the Term to the map
                                for (int j = head; j <= curPos; j++) {
                                    matchedTermList = map.get(j);
                                    if (matchedTermList == null) {
                                        /*
                                         * the i-th char is not matched to any
                                         * term create a singleton term list.
                                         * TODO: I don't know why singletonList
                                         * does NOT work... so, use this stupid
                                         * way instead.
                                         */
                                        List<Term> tempArray = new ArrayList<Term>(1);
                                        tempArray.add(term);
                                        map.put(j, tempArray);
                                    } else {
                                        // the i-th char is ever matched,
                                        // just add to the tail.
                                        matchedTermList.add(term);
                                    }
                                }// for
                                term.positions.add(head);
                                tempTermList.add(term);
                                tempTermPosList.add(head
                                        - (curPos - senLen + 1));
                                termOccurs[i]++;
                                senTermCount++;
                            }// if
                            break;
                        } else {
                            // An incorrect char, not the Term I am trying
                            // to recognize
                            if (termStates[i] == 0)
                                break;
                            termStates[i] = term.kmpLink[termStates[i] - 1] + 1;
                        }// else
                    }// while
                }

                // recognizing block, like (),
                // notice that "abc" is also considered to be a block, so the following
                // statememnts must be in this order to deal with the case of "", 
                // in which, leftBrace equals to rightBrace.
                if (inBlock && curPos > posBlock + policy.MAX_BLOCK_LENGTH)
                    inBlock = false;
                
                if (inBlock && rightBraces.indexOf(curChar) > -1)
                    inBlock = false;

                if (leftBraces.indexOf(curChar) > -1) {
                    inBlock = true;
                    posBlock = curPos;
                }
                    
                // through sentence is longer than senThreshold3,
                // but curChar is in term or word or num serial
                if (curPos < (text.length() - 1)
                        && (senLen <= maxSentenceLength || (senLen > maxSentenceLength && (inTerm
                                || inWord || inNumSerial))))
                    continue;
            }// if

            int senHead = curPos - senLen + 1;

            // a new sentence
            int termTypes = 0;
            for (int i = 0; i < termList.size(); i++)
                if (termOccurs[i] > 0)
                    termTypes++;
            currentSentence = new Sentence(senCount++, text, senHead, senLen,
                    senWidth, termTypes, tempTermList, tempTermPosList);

            // try to figure out if a sentence is start of a new paragraph or
            // end of a
            // paragraph
            // by the way, try to determin the sentence distance between 2
            // sentences.
            currentSentence.setPrevDist(sentDistance);
            currentSentence.setPrev(previousSentence);
            if (previousSentence != null) {
                if (curChar == '\n')
                    previousSentence.setPositionWeight(Sentence.POSITION_WEIGHT_ENDING);
                previousSentence.setSuccDist(sentDistance);
                previousSentence.setSucc(currentSentence);
            }
            if (sentences.size() == 0 || curChar == '\n') {
                currentSentence.setPositionWeight(Sentence.POSITION_WEIGHT_BEGINNING);
            }

            sentences.add(currentSentence);
            previousSentence = currentSentence;

            // set local variables for a new sentence
            senTermCount = 0;
            senLen = 0;
            senWidth = 0;
            sentDistance = 0;
            tempTermList.clear();
            tempTermPosList.clear();
            for (int i = 0; i < termList.size(); i++) {
                termStates[i] = 0;
                termOccurs[i] = 0;
            }// for
            // set initial values of local variables for new sentence.
            inUrl = false;
            inAlnum = false;
            inBlock = false;
            posBlock = 0;
            inWord = false;
            inNumSerial = false;
            inTerm = false;
        } // for curPos from 0 to text.length()
        if (currentSentence != null) {
            currentSentence.setPrevDist(sentDistance);
            currentSentence.setPositionWeight(Sentence.POSITION_WEIGHT_ENDING);
        }
        return sentences;
    }

    /**
     * extend suspension before currently existing suspension.
     * 
     * @param widthTolerance
     *      tolerance in width
     */
    private void extendSuspension(char[] text, int[] flag, double[] attractive,
            int[] pair, List<Integer> susIndex, int segmentCount,
            int widthTolerance) {
        final int MIN_INTERVAL_LENGTH = 4;
        int width = 0;
        for (int i = 0; i < text.length; i++) {
            if (flag[i] != FLAG_SUSPENSION)
                width += getCharWidth(text[i]);
        }
        // find cold interval
        Interval cold = findColdIntervalNearSuspension(text, flag, attractive,
                pair, susIndex, segmentCount, MIN_INTERVAL_LENGTH * HANZI_WIDTH, 
                width - summaryWidth);
        if (cold != null) {
            // refine
            for (int i = cold.start; i <= cold.end; i++) {
                flag[i] = FLAG_SUSPENSION;
            }
        }

    }

    /**
     * find the coldest interval near suspension
     * the length of interval is longer than MIN_INTERVAL_LENGTH
     * minReduce, maxReduce are measured in pixel-width.

     * @param text
     * @param flag
     * @param attractive
     * @param pair
     * @param susIndex
     * @param segmentCount
     * @param minReduce
     *      minimum width of the interval
     * @param maxReduce
     *      maximum width of the interval
     * @return
     */
    private Interval findColdIntervalNearSuspension(char[] text, int[] flag,
            double[] attractive, int[] pair, List<Integer> susIndex,
            int segmentCount, int minReduce, int maxReduce) {
        assert (flag.length == attractive.length);

        int length = flag.length;
        List<Integer> lefts = new ArrayList<Integer>();
        List<Integer> rights = new ArrayList<Integer>();
        List<Integer> reduce = new ArrayList<Integer>();
        // expand from the end
        if (flag[length - 1] != FLAG_SUSPENSION) {
            int i = length - 1;
            int r = 0;
            while (i >= 0 && flag[i] == FLAG_SUSPENSION)
                i--;
            while (r < maxReduce && i >= 0 && attractive[i] < 0) {
                int leftBound = Math.min(i, pair[i]) - 1;
                boolean canContinue = true;
                for (int j = leftBound + 1; j <= i; j++) {
                    if (attractive[j] > 0) {
                        canContinue = false;
                        break;
                    }
                }
                if (!canContinue)
                    break;
                for (int j = i; j > leftBound; j--) {
                    r += getCharWidth(text[j]);
                }
                i = leftBound;
            }
            lefts.add(i + 1);
            rights.add(length - 1);
            reduce.add(r);
        }
        // find every possible interval
        for (int index: susIndex) {
            int i = index;
            int r = 0;
            while (i >= 0 && flag[i] == FLAG_SUSPENSION)
                i--;
            while (r < maxReduce && i >= 0 && attractive[i] < 0) {
                int leftBound = Math.min(i, pair[i]) - 1;
                boolean canContinue = true;
                for (int j = leftBound + 1; j <= i; j++) {
                    if (attractive[j] > 0) {
                        canContinue = false;
                        break;
                    }
                }
                if (!canContinue)
                    break;
                for (int j = i; j > leftBound; j--) {
                    r += getCharWidth(text[j]);
                }
                i = leftBound;
            }
            lefts.add(i + 1);
            i = index;
            while (i < length && flag[i] == FLAG_SUSPENSION)
                i++;
            while (r < maxReduce && i < length && attractive[i] < 0) {
                int deltaWidth = 0;
                boolean canContinue = true;
                for (int j = i; j <= pair[i]; j++) {
                    deltaWidth += getCharWidth(text[j]);
                    if (attractive[j] > 0)
                        canContinue = false;
                }
                if (!canContinue)
                    break;
                r += deltaWidth;
                i = pair[i] + 1;
                while (i < length && flag[i] != FLAG_SUSPENSION
                        && (notAfterSuspension.indexOf(text[i]) >= 0)) {
                    i++;
                    r += getCharWidth(text[i]);
                }
            }
            rights.add(i - 1);
            reduce.add(r);
        }
        int max = minReduce, maxReduceIndex = -1;
        for (int i = 0; i < reduce.size(); i++) {
            if (reduce.get(i) > max) {
                max = reduce.get(i);
                maxReduceIndex = i;
            }
        }
        if (maxReduceIndex == -1)
            return null;
        else
            return new Interval(lefts.get(maxReduceIndex), rights
                    .get(maxReduceIndex));
    }

    /**
     * @param request
     * @param text
     * @return
     */
    public String getSummary(String request, String text) {
        return getSummary(request, text, SummaryType.WEB_SEARCH_SUMMARY);
    }

    /**
     * 
     * @param request
     * @param text
     * @param summaryLength
     * @return
     */
    public String getSummary(String request, String text, int summaryLength) {
        this.summaryLength = summaryLength;
        return getSummary(request, text, SummaryType.WEB_SEARCH_SUMMARY);
    }

    /**
     * 
     * @param request
     * @param text
     * @param policy
     * @return
     */
    public String getSummary(String request, String text, SummaryPolicy policy) {
        text = preFilter(new StringBuilder(text), policy);
        if (text.length() == 0) {
            resultSummary = new StringBuilder("");
        } else {
            terms = divideTerms(request);
            sentences = divideSentences(text, terms, policy);
            for (Term term: terms) {
                term.computeTermWeight();
            }
            int[] selected;
            Sentence.setPreferredSenLength(policy.PREFERRED_SEN_LENGTH);
            selected = selectSentences(sentences, policy);
            composeSummary(sentences, selected, policy);
            resultSummary = postFilter(resultSummary);
        }
        computeSummaryWidth();
        return resultSummary.toString();
    }

    /**
     * 
     * @param request
     * @param text
     * @param policy
     * @param summaryLength
     * @return
     */
    public String getSummary(String request, String text, SummaryPolicy policy, int summaryLength) {
        this.summaryLength = summaryLength;
        return getSummary(request, text, policy);
    }
    
    /**
     * @param request
     * @param text
     * @param type
     * @return
     */
    public String getSummary(String request, String text, SummaryType type) {
        SummaryPolicy policy;
        // if use longSummary policy, otherwise, use shortSummary policy
        if (summaryLength > LONG_SUMMARY_THRESHOLD)
            policy = longSummaryPolicy; 
        else
            policy = shortSummaryPolicy;
        
        if (type == SummaryType.WEB_SEARCH_SUMMARY) {
            // load settings for web search summary
        } else if (type == SummaryType.BLOG_SEARCH_SUMMARY) {
            // load settings for blog search summary
        } else if (type == SummaryType.IMAGE_SEARCH_SUMMARY) {
            policy = shortSummaryPolicy;
            // load settings for image search summary
        } else {
            // load settings for defaut
        }
        return getSummary(request, text, policy);
    }

    /**
     * @param request,
     *            query terms seperated by TERM_LIST_SEPARATOR;
     * @param text,
     *            the text to be summarizered;
     * @param type,
     *            indicate where this summary is used.
     * @return , the summary result
     */
    public String getSummary(String request, String text, String type) {
        SummaryType flag;
        if (type.toUpperCase().equals("IMAGE")) {
            // load settings for image search summary
            flag = SummaryType.IMAGE_SEARCH_SUMMARY;
        } else if (type.toUpperCase().equals("WEB")) {
            // load settings for web search summary
            flag = SummaryType.WEB_SEARCH_SUMMARY;
        } else if (type.toUpperCase().equals("BLOG")) {
            // load settings for blog search summary
            flag = SummaryType.BLOG_SEARCH_SUMMARY;
        } else {
            // load settings for defaut, currently, take web search as default.
            flag = SummaryType.WEB_SEARCH_SUMMARY;
        }
        return getSummary(request, text, flag);
    }
    
    /**
     * 
     * @param request
     * @param text
     * @param type
     * @param summaryLength
     * @return
     */
    public String getSummary(String request, String text, String type, int summaryLength) {
        this.summaryLength = summaryLength;
        return getSummary(request, text, type);
    }

    /**
     * get summary width
     * @return width of summary
     */
    public int getSummaryWidth() {
       return actualWidth; 
    }

    // if there's no term matched in the text.
    private boolean noTermMatched() {
        for (Term term: terms) {
            if (term.getAppearTimes() > 0)
                return false;
        }
        return true;
    }

    /**
     * remove short segment at beginning or end of the summary or suspension
     * e.g. 非议,觉得因为就是广州唱区有三个人,然后是我们有两个人可以给广州的选手投票,所
     * is revised and set to
     * ...觉得因为就是广州唱区有三个人,然后是我们有两个人可以给广州的选手投票...
     */
    private void reviseSummary(char[] text, int[] flag, int[] pair, double[] attractive, 
            List<Integer> susIndex, SummaryPolicy policy) {
        int length = text.length;
        // remove at the beginning
        int bodyStart = 0;
        while (bodyStart < text.length && flag[bodyStart] == FLAG_SUSPENSION) {
            bodyStart++;
        }
        if (bodyStart < text.length) {
            tryReviseInterval(text, flag, pair, attractive, bodyStart, 1, policy.SUMMARY_REVISE_LENGTH);
        }
        for (Integer index : susIndex) {
            int left = index;
            while (left >= 0 && flag[left] == FLAG_SUSPENSION)
                left--;
            if (left >= 0) {
                tryReviseInterval(text, flag, pair, attractive, left, -1, policy.SUMMARY_REVISE_LENGTH);
            }
            int right = index;
            while (right < length && flag[right] == FLAG_SUSPENSION)
                right++;
            if (right < length) {
                tryReviseInterval(text, flag, pair, attractive, right, 1, policy.SUMMARY_REVISE_LENGTH);
            }
        }
        // revise from the end
        int i = text.length - 1;
        boolean meetSuspention = false;
        while (i > 0 && (flag[i] == FLAG_SUSPENSION || flag[i] == 0 
                && Character.isWhitespace(text[i]))) {
            if (flag[i] == FLAG_SUSPENSION)
                meetSuspention = true;
            if (meetSuspention)
                flag[i] = FLAG_SUSPENSION;
            else 
                flag[i] = FLAG_BLANK;
            i--;
        }
        if (i >= 0) {
            if (SEN_DIVIDERS.indexOf(text[i]) >= 0) {
                for (int j = i + 1; j < text.length; j++)
                    flag[j] = FLAG_BLANK ;
            }
            else if (SEN_SUBDIVIDERS.indexOf(text[i]) >= 0)
                flag[i] = FLAG_SUSPENSION;
        }
    }

    /**
     * Generate summary from the beginning of text. In case that no term is found in the
     * text.
     */
    private StringBuilder selectFromStart(List<Sentence> sentences, int lengthTolerance) {
        int width = 0;
        int i = 0;  
        StringBuilder sb = new StringBuilder();
        while (width + 3 * HANZI_WIDTH < summaryWidth) {
            if (i >= sentences.size())
                break;
            Sentence sen = sentences.get(i++);
            int senWidth = sen.getWidth();
            if (width + 3 * HANZI_WIDTH + senWidth <= summaryWidth) {
                sb.append(sen.getText());
                width += senWidth;
            } else {
                int j = 0;
                char ch;
                while (width + 3 * HANZI_WIDTH <= summaryWidth) {
                    if (j >= sen.getLength())
                        break;
                    ch = sen.getCharAt(j++);
                    width += getCharWidth(ch);
                    sb.append(ch);
                }
            }
        }
        sb.append("...");
        return sb;
    }

    /**
     * select a few sentences to make up a sketch of summary (initial summary).
     * 
     * @param sentences
     * @return
     */
    private int[] selectSentences(List<Sentence> sentences, SummaryPolicy policy) {
        int totalWidth = 0;
        // if a serial of sentence is approximately the required length, we need
        // NOT continue adding sentences, if we do continue, we may get a serial
        // of sentence whose total length is much larger than expected, in that
        // case, we have to add suspesion ("...") to shorten it. However, the
        // total length in increased by length of "..." and at least word. here,
        // we use "..." + " " as our tolerance of summary length. the total
        
        // length should be between [summaryLength - tolerance, summaryLength].\
        // int widthTolerance = policy.LENGTH_TOLERANCE * HANZI_WIDTH;
        
        // total segment count, maybe useful when limiting the maximum segment
        // count of a summary
        int segmentCount = 0;
        List<Integer> selected = new ArrayList<Integer>();
        Map<Term, Integer> selectedTerms = new HashMap<Term, Integer>();
        while (totalWidth < summaryWidth) {
            double maxRank = 0;
            int maxIndex = -1;
            Sentence maxSentence = null;
            for (int i = 0; i < sentences.size(); i++) {
                Sentence sentence = sentences.get(i);
                // if the sentence is already selected or segment count equals
                // to MAX and selecting this sentence will result in increasing
                // of segment count, then just ignore this
                if (sentence.isSelected()
                        || segmentCount == policy.MAX_SEGMENT_COUNT
                        && !sentence.isConnected())
                    continue;
                sentence.computeRank(selectedTerms);
                double rank = sentence.getRank();
                if (rank > maxRank) {
                    maxRank = rank;
                    maxIndex = i;
                    maxSentence = sentence;
                }
            }
            if (maxIndex >= 0) {
                selected.add(maxIndex);
                totalWidth += maxSentence.getWidth();
                maxSentence.setSelected(true);
                for (Term term: maxSentence.termList) {
                    Integer times = selectedTerms.get(term);
                    if (times == null)
                        selectedTerms.put(term, 1);
                    else
                        selectedTerms.put(term, times + 1);
                }
                // update segment count
                // if current sentence is connected to previous OR succeeding
                // sentence,
                // segmentCount should not be the same as before.
                // if as is connected to privious AND succedding sentence,
                // segmentCount should be less than before.
                segmentCount++;
                Sentence temp = maxSentence.getPrev();
                if (temp != null) {
                    if (temp.isSelected())
                        segmentCount--;
                    temp.computeRank(selectedTerms);
                }
                temp = maxSentence.getSucc();
                if (temp != null) {
                    if (temp.isSelected())
                        segmentCount--;
                    temp.computeRank(selectedTerms);
                }
            } else
                break;

        }
        Collections.sort(selected);
        int[] result = new int[selected.size()];
        for (int i = 0; i < selected.size(); i++) {
            result[i] = selected.get(i);
        }
        return result;
    }

    /**
     * set max length for a single sentence in the summary.
     * 
     * @param maxSentenceLength
     */
    public void setMaxSenLength(int maxSentenceLength) {
        this.maxSentenceLength = maxSentenceLength;
    }

    /**
     * set max length for summary.
     * 
     * @param summaryLength
     */
    public void setSummaryLength(int summaryLength) {
        this.summaryLength = summaryLength;
        // in case that users may use Integer.MAX_VALUE as the expected summary length,
        // which is actually absolutely an upper bound for any applicable case,
        // when calculating summaryWidth, we use 
        //      min(Integer.Mav_Value, summaryLength * HANZI_WIDTH)
        // note that an applicable case is most likely to be far less than Integer.MAX_Value
        if (summaryLength > SUMMARY_LENGTH_UPPER_BOUND)
            this.summaryWidth = SUMMARY_LENGTH_UPPER_BOUND;
        else
            this.summaryWidth = summaryLength * HANZI_WIDTH;
    }

    /**
     * try to remove a veryshort segment
     * @param index initial index;
     * @param delta forward or backward; 
     */ 
    private void tryReviseInterval(char[] text, int[] flag, int[] pair, double[] attractive, 
            int index, int delta, int reviseLength) {
        boolean canRemove = false;
        int endIndex = index;
        for (int i = 1; i <= reviseLength; i++) {
            if (endIndex < 0 || endIndex >= text.length) {
                canRemove = true;
                break;
            }
            char curChar = text[endIndex];
            if (delta > 0 && isLeftPunctChar(curChar) || 
                    delta < 0 && isRightPunctChar(curChar)) {
                canRemove = false;
                break;
            }
            if (flag[endIndex] > 0) {
                // meet a term
                break;
            } else if (flag[endIndex] == FLAG_SUSPENSION || 
                    REVISE_PUNCTIONS.indexOf(curChar) >= 0 || 
                    delta > 0 && isRightPunctChar(curChar) ||
                    delta < 0 && isLeftPunctChar(curChar)) {
                canRemove = true;
                break;
            } else if (isLetterOrDigit(curChar)) {
                canRemove = false;
                break;
            }
            endIndex += delta;
        }
        if (canRemove) {
            while (index != endIndex) {
                flag[index] = FLAG_SUSPENSION;
                index += delta;
            }
            if (endIndex >= 0 && endIndex < text.length)
                flag[endIndex] = FLAG_SUSPENSION;
        }
    }

    private boolean isRightPunctChar(char c) {
        return c != '\'' && c != '\"' && rightBraces.indexOf(c) >= 0;
    }

    private boolean isLeftPunctChar(char c) {
        return c != '\'' && c != '\"' && leftBraces.indexOf(c) >= 0;
    }

}

/**
 * closed interval [start, end]
 */
class Interval {
    public int start;

    public int end;

    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

/**
 * sentence is part of a article. we consider it to be important part of summary.
 * actually, it's basic element of summary.
 * @author zhoumin
 *
 */
class Sentence {
    /**
     * all sentence weight should be in the interval [0.0, 2.0], 
     * except FRESH_TERM_WEIGHT, which grows exponential in fresh term count.
     */
    // importance of sentence, decided by the position of the sentence in the
    // paragraph.
    public static final double POSITION_WEIGHT_BEGINNING = 1.2;

    public static final double POSITION_WEIGHT_ENDING = 1.2;

    // criteria for head and tail
    private static final int HEAD_TAIL_RANGE = 4;

    // weight for the first and last 4 chars for a matched char.
    private static final double HEAD_TAIL_WEIGHT = 1.6;

    // addition rank for the sentence, if it's privious or(and) succeeding
    // sentence is also selected.
//    private static final double PREV_CONNECTED_WEIGHT = 1.5;
//    private static final double SUCC_CONNECTED_WEIGHT = 1.2;
//    private static final double PREV_AND_SUCC_CONNECTED_WEIGHT = 2.0;

//    // addtion rank for sentence, if it introduce a new term, the rank is
//    // FRESH_TERM_WEIGHT times original rank.
//    private static final double FRESH_TERM_WEIGHT = 3;

    private static final String UNWELCOME_CHARS = "|\t: ，：%#";
    
    // 8 as default. remember to change it before computing rank.
    private static int preferredSenLength = 8;

    public static void setPreferredSenLength(int preferredLength) {
        preferredSenLength = preferredLength;
    }

    // sentence ID
    public final int senId;

    // the original text which contain the sentence.
    public final String buffer;

    // matched terms, including duplicated terms.
    public final List<Term> termList = new ArrayList<Term>();

    // position related to the start of the sentence.
    public final List<Integer> termPosList = new ArrayList<Integer>();

    // public final int senId; // the ID of the sentence, starting from 0
    public final int head; // the start position of the sentence

    private int length; // the sentence's length

    private int width; // the sentence's width

    private int termTypes; // the number of term types in this sentence

    private double termMatchingRank; // rank by matching terms, part of total

    private double commuRank; // rank can be passed to nearby sentence. we ignore termMatchingRank here.
    
    private double rank; // the rank of the sentence

    private Sentence prev, succ; // previous and succeeding sentences.

    // previous and succeeding distance between sentences.
    private double prevDist, succDist;

    /**
     * importance of the sentence if the sentence is at the beginning of the
     * paragraph, or at the end of the paragraph, it's consider to be more
     * important than ones in the middle. for beginning, weight = 1.5; for
     * ending, weight = 1.5; otherwise, weight = 1.0;
     */
    private double positionWeight = 1.0;

    // whether selected
    private boolean selected;

    private double readabilityWeight;

    // constructor
    public Sentence(int senId, String buffer, int head, int length, int width,
            int termTypes, List<Term> termList, List<Integer> termPosList) {
        this.senId = senId;
        this.buffer = buffer;
        this.head = head;
        this.length = length;
        this.width = width;
        this.termList.addAll(termList);
        this.termPosList.addAll(termPosList);
        this.termTypes = termTypes;
        termMatchingRank = computeTermMatchingRank();
        computeReadabilityWeight();
    }

    /*
     * compute rank for a sentence when selectedTerms are already selected
     */
    public double computeRank(Map<Term, Integer> selectedTerms) {
        // use this formula to compute rank of sentence:
        // rank = termMatchingRank * termTypes * if_selected(prev, succ) / sqrt(length);
        // gap and sentenceDistance are also considered.
//        double connectionWeight = 0;
//        int connectionCount = 0;
//        if (prev != null && prev.selected) {
//            connectionWeight = PREV_CONNECTED_WEIGHT;
//            connectionCount++;
//        }
//        if (succ != null && succ.selected) {
//            connectionWeight = SUCC_CONNECTED_WEIGHT;
//            connectionCount++;
//        }
//        if (connectionCount == 2)
//            connectionWeight = PREV_AND_SUCC_CONNECTED_WEIGHT;
//        else if (connectionCount == 0)
//            connectionWeight = 1;
//        
        double connectionRank = 0;
        int connectionCount = 0;
        if (prev != null && prev.selected) {
            connectionRank += prev.getCommuRank() / 2 + 1;
            connectionCount++;
        }
        if (succ != null && succ.selected) {
            connectionRank += succ.getCommuRank() / 2;
            connectionCount++;
        }
        /* compute variationWeight;
         * see, how many different terms it introduces. whenever a new term is 
         * introduced, multiply the rank of sentence by VARIATION_WEIGHT;
         */
        double freshTermRank;
        int freshTermLength = 0;
        int freshTermCount = 0;
        if (selectedTerms != null) {
            for (Term term: termList) {
                Integer times = selectedTerms.get(term);
                if (times == null) {
                    freshTermCount++;
                    freshTermLength += term.length;
                }
            }
        }
        freshTermRank = Math.exp(freshTermCount) * (1 + freshTermLength);

        // add connectionWeight, so that a "nearby" sentence can have a positive
        // rank instead of 0.
        if (termMatchingRank == 0) {
            commuRank = readabilityWeight * readabilityWeight * readabilityWeight * readabilityWeight
                    * (connectionRank + 1.0 / (senId + 2));
        } else {
            commuRank = readabilityWeight * (positionWeight * (termMatchingRank * termTypes) / length
                            + connectionRank + 1.0 / (senId + 2));
        }
        // magic number here, in fact, any "big" number larger than a common communicable
        // weight will work. here, we choose 100000.0 just for convenience;
        rank = commuRank + freshTermRank * 100000.0;
        return rank;
    }

    // readability weight.
    private void computeReadabilityWeight() {
        int unWelcomeChars = 0;
        // preserved for further development.
        int subDividerCount = 0;
        for (int i = head; i < head + length; i++) {
            if (UNWELCOME_CHARS.indexOf(buffer.charAt(i)) >= 0) {
                unWelcomeChars++;
            }
            if (Summary.SEN_SUBDIVIDERS.indexOf(buffer.charAt(i)) >= 0) {
                subDividerCount++;
            }
        }
        // this function is preserved for further development.
        // right now, just use this simple way.
        double weight;
        if (length < preferredSenLength) {
            weight = 0.9;
        } else {
            weight = 1;
        }
        readabilityWeight = weight / (1 + (double)(unWelcomeChars + subDividerCount) / length);
    }

    private double computeTermMatchingRank() {
        /*
         * 1) the first and last 4 chars are considered to be important
         * ####...#### 
         * 2) for every char, whenever it can be matched by a term,
         * add the appropriate weight to the sentence's matching rank with the
         * term's matching weight.
         */
        double matchingRank = 0;
        for (int i = 0; i < termList.size(); i++) {
            Term term = termList.get(i);
            int startPos = termPosList.get(i);
            for (int j = 0; j < term.length; j++) {
                int pos = j + startPos;
                if (pos < HEAD_TAIL_RANGE || j > term.length - HEAD_TAIL_RANGE)
                    matchingRank += term.getTermWeight() * HEAD_TAIL_WEIGHT;
                else
                    matchingRank += term.getTermWeight();
            }
        }
        return matchingRank;
    }

    // return the char at posisiont of index, index is related to the start of
    // sentence.
    public char getCharAt(int index) {
        return buffer.charAt(head + index);
    }

    public int getLength() {
        return length;
    }

    public double getPositionWeight() {
        return positionWeight;
    }

    public Sentence getPrev() {
        return prev;
    }

    public double getPrevDist() {
        return prevDist;
    }

    public double getRank() {
        return rank;
    }

    public Sentence getSucc() {
        return succ;
    }

    public double getSuccDist() {
        return succDist;
    }

    public double getTermMatchingRank() {
        return termMatchingRank;
    }

    // return the content of the sentence as a string.
    public String getText() {
        return buffer.substring(head, head + length);
    }

    public int getWidth() {
        return width;
    }

    // if connected to previous OR succeeding sentence
    public boolean isConnected() {
        return isPrevConnected() || isSuccConnected();
    }

    // if connected to previous sentence
    public boolean isPrevConnected() {
        return (prev != null && prev.isSelected());
    }

    public boolean isSelected() {
        return selected;
    }

    // if connected to succeeding sentence
    public boolean isSuccConnected() {
        return (succ != null && succ.isSelected());
    }

    public void setPositionWeight(double importance) {
        this.positionWeight = importance;
    }

    public void setPrev(Sentence prev) {
        this.prev = prev;
    }

    public void setPrevDist(double prevDist) {
        this.prevDist = prevDist;
    }

    public void setSelected(boolean selected) {
        this.selected = selected;
    }

    public void setSucc(Sentence succ) {
        this.succ = succ;
    }

    public void setSuccDist(double succDist) {
        this.succDist = succDist;
    }

    public double getCommuRank() {
        return commuRank;
    }

}// Sentence

/**
 * class term
 * @author zhoumin
 *
 */
class Term {
    // divide terms by TERM_LIST_SEPARATOR
    public static final char TERM_LIST_SEPARATOR = ' ';

    public final int originalPosition;

    public final int[] kmpLink;

    public final String buffer;

    public final int length;

    // record where the term appeared, in which sentence
    public final List<Integer> sentences = new ArrayList<Integer>();

    // record where the term appeared, the relative position to the head
    public final List<Integer> positions = new ArrayList<Integer>();

    // termWeight = 1 / termFrequency = 1 / appears.size();
    // how important the term is. the more it appears, the more important it is
    // to the text, but for a single appearnce, it's less important than a less
    // appeared term. this term need to be computed before using. just call
    // computeTermWeight.
    private double termWeight = 1;

    // constructor
    public Term(String buffer, int originalPosition) {
        this.buffer = buffer;
        this.originalPosition = originalPosition;
        this.length = extendLength(buffer, originalPosition);
        kmpLink = computeKmpLink(buffer, originalPosition, length);
    }

    // compute KMP link of substring of buffer, say buffer[p..len-1]
    private int[] computeKmpLink(String buffer, int p, int len) {
        // kmpLink[i] means if text fails to match pattern[i], then what is the
        // next index of pattern to which we try to match text
        int[] kmpLink = new int[len + 1];
        Arrays.fill(kmpLink, 0);
        kmpLink[0] = -1;

        for (int i = 1; i < len; i++) {
            int k = kmpLink[i - 1] + 1;
            while (k > 0 && buffer.charAt(p + i - 1) != buffer.charAt(p + k - 1)) {
                k = kmpLink[k - 1] + 1;
            }
            kmpLink[i] = k;
        }
        return kmpLink;
    }

    public void computeTermWeight() {
        int times = getAppearTimes();
        if (times == 0)
            termWeight = 1;
        else
            termWeight = 1 / times;
        /**
         * actually, we can use following ranking formula, anyway, that depends.
         * termWeight = 1 / Math.sqrt(getAppearTimes()); 
         */
    }

    // try to locate the end of term and return the length of the term.
    private int extendLength(String s, int p) {
        int endPos = s.indexOf(TERM_LIST_SEPARATOR, p + 1);
        if (endPos == -1)
            return s.length() - p;
        else
            return endPos - p;
    }

    public int getAppearTimes() {
        return positions.size();
    }

    public char getCharAt(int index) {
        return buffer.charAt(originalPosition + index);
    }

    public double getTermWeight() {
        return termWeight;
    }

    public Object getText() {
        return buffer.substring(originalPosition, originalPosition + length);
    }

}
